<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.1">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/%E6%AD%A6%E6%B1%8932x32.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/%E6%AD%A6%E6%B1%8916x16.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">


<link rel="stylesheet" href="/lib1/font-awesome/css/all.min.css">
  <link rel="stylesheet" href="/lib1/pace/pace-theme-center-simple.min.css">
  <script src="/lib1/pace/pace.min.js"></script>

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"example.com","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="双指针技巧详解主要分为两类：1、快慢指针；2、左右指针；前者主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或字符串）中的问题，比如：二分查找。 链表、子串、数组的题目，一般都需要用到双指针技巧。 链表指针数组题，用双指针别犹豫。 双指针家三兄弟，各个都是万人迷。 快慢指针最神奇，链表操作无压力。 归并排序找中点，链表成环搞判定。 左右指针最常见，左右两端相向行。 反转数组">
<meta property="og:type" content="article">
<meta property="og:title" content="双指针查找与常用算法框架">
<meta property="og:url" content="http://example.com/2020/09/29/%E7%AE%97%E6%B3%95/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/index.html">
<meta property="og:site_name" content="Technological Blog">
<meta property="og:description" content="双指针技巧详解主要分为两类：1、快慢指针；2、左右指针；前者主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或字符串）中的问题，比如：二分查找。 链表、子串、数组的题目，一般都需要用到双指针技巧。 链表指针数组题，用双指针别犹豫。 双指针家三兄弟，各个都是万人迷。 快慢指针最神奇，链表操作无压力。 归并排序找中点，链表成环搞判定。 左右指针最常见，左右两端相向行。 反转数组">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://example.com/image/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/image-20210909211423726.png">
<meta property="article:published_time" content="2020-09-29T09:30:23.000Z">
<meta property="article:modified_time" content="2021-11-03T08:29:48.718Z">
<meta property="article:author" content="Li Yudong">
<meta property="article:tag" content="算法框架">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://example.com/image/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/image-20210909211423726.png">

<link rel="canonical" href="http://example.com/2020/09/29/%E7%AE%97%E6%B3%95/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true,
    lang   : 'zh-CN'
  };
</script>

  <title>双指针查找与常用算法框架 | Technological Blog</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <h1 class="site-title">Technological Blog</h1>
      <span class="logo-line-after"><i></i></span>
    </a>
      <p class="site-subtitle" itemprop="description">IT小白的成长之旅</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>




<nav class="site-nav">
  <ul id="menu" class="main-menu menu">
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="user fa-fw"></i>关于</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="tags fa-fw"></i>标签<span class="badge">18</span></a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="th fa-fw"></i>分类<span class="badge">14</span></a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="archive fa-fw"></i>归档<span class="badge">95</span></a>

  </li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
  <span class="search-icon">
    <i class="fa fa-search"></i>
  </span>
  <div class="search-input-container">
    <input autocomplete="off" autocapitalize="off"
           placeholder="搜索..." spellcheck="false"
           type="search" class="search-input">
  </div>
  <span class="popup-btn-close">
    <i class="fa fa-times-circle"></i>
  </span>
</div>
<div id="search-result">
  <div id="no-result">
    <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
  </div>
</div>

    </div>
  </div>

</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>

  <a href="https://github.com/tiarmor1" class="github-corner" title="Follow me on GitHub" aria-label="Follow me on GitHub" rel="noopener" target="_blank"><svg width="80" height="80" viewBox="0 0 250 250" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"></path><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin: 130px 106px;" class="octo-arm"></path><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"></path></svg></a>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content post posts-expand">
            

    
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://example.com/2020/09/29/%E7%AE%97%E6%B3%95/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/author.jpg">
      <meta itemprop="name" content="Li Yudong">
      <meta itemprop="description" content="">
    </span>
    
    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="Technological Blog">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          双指针查找与常用算法框架
        </h1>
    
        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-calendar"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
    
              <time title="创建时间：2020-09-29 17:30:23" itemprop="dateCreated datePublished" datetime="2020-09-29T17:30:23+08:00">2020-09-29</time>
            </span>
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="far fa-calendar-check"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2021-11-03 16:29:48" itemprop="dateModified" datetime="2021-11-03T16:29:48+08:00">2021-11-03</time>
              </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="far fa-folder"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
                </span>
            </span>
    
          
    
        </div>
      </header>
    
    
    
    
    <div class="post-body" itemprop="articleBody">
    
      
        <h1 id="双指针技巧详解"><a href="#双指针技巧详解" class="headerlink" title="双指针技巧详解"></a>双指针技巧详解</h1><p>主要分为两类：1、快慢指针；2、左右指针；前者主要解决链表中的问题，比如典型的判定链表中是否包含环；后者主要解决数组（或字符串）中的问题，比如：二分查找。</p>
<p>链表、子串、数组的题目，一般都需要用到双指针技巧。</p>
<p>链表指针数组题，用双指针别犹豫。</p>
<p>双指针家三兄弟，各个都是万人迷。</p>
<p>快慢指针最神奇，链表操作无压力。</p>
<p>归并排序找中点，链表成环搞判定。</p>
<p>左右指针最常见，左右两端相向行。</p>
<p>反转数组要靠它，二分搜索是弟弟。</p>
<p>滑动窗口老猛男，子串问题全靠它。</p>
<p>左右指针滑窗口，一前一后齐头进。</p>
<h2 id="快慢指针的用法"><a href="#快慢指针的用法" class="headerlink" title="快慢指针的用法"></a>快慢指针的用法</h2><p>快慢指针一般都初始化指向链表的头节点head，前进时快指针fast在前，慢指针slow在后，从而巧妙解决链表中问题。</p>
<p><img src="/image/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/image-20210909211423726.png" alt="image-20210909211423726"></p>
<h3 id="判定链表中是否有环"><a href="#判定链表中是否有环" class="headerlink" title="判定链表中是否有环"></a>判定链表中是否有环</h3><p>单链表的特点是每个节点只知道下⼀个节点，所以⼀个指针的话⽆法判断链 表中是否含有环的。 如果链表中不含环，那么这个指针最终会遇到空指针 null 表⽰链表到头 了，这还好说，可以判断该链表不含环。但是如果链表中含有环，那么这个指针就会陷⼊死循环，因为环形数组中没 有 null 指针作为尾部节点。 </p>
<p>经典解法就是⽤两个指针，⼀个跑得快，⼀个跑得慢。如果不含有环，跑得 快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终 会超慢指针⼀圈，和慢指针相遇，说明链表含有环。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">hasCycle</span><span class="params">(ListNode head)</span> </span>&#123; </span><br><span class="line">    ListNode fast, slow; </span><br><span class="line">    fast = slow = head; </span><br><span class="line">    <span class="keyword">while</span> (fast != null &amp;&amp; fast.next != null) &#123; </span><br><span class="line">        fast = fast.next.next; </span><br><span class="line">        slow = slow.next; </span><br><span class="line">        <span class="keyword">if</span> (fast == slow) <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="已知链表中有环，返回其起始位置"><a href="#已知链表中有环，返回其起始位置" class="headerlink" title="已知链表中有环，返回其起始位置"></a>已知链表中有环，返回其起始位置</h3><p>可以看到，当快慢指针相遇时，让其中任⼀个指针指向头节点，然后让它俩 以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。</p>
<p>第⼀次相遇时，假设慢指针 slow ⾛了 k 步，那么快指针 fast ⼀定⾛了 2k 步，也就是说⽐ slow 多⾛了 k 步（也就是环的⻓度）。设相遇点距环的起点的距离为 m，那么环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。 巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。 所以，只要我们把快慢指针中的任⼀个重新指向 head，然后两个指针同速 前进，k - m 步后就会相遇，相遇之处就是环的起点了</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">ListNode <span class="title">detectCycle</span><span class="params">(ListNode head)</span> </span>&#123; </span><br><span class="line">    ListNode fast, slow; </span><br><span class="line">    fast = slow = head; </span><br><span class="line">    <span class="keyword">while</span> (fast != null &amp;&amp; fast.next != null) &#123; </span><br><span class="line">        fast = fast.next.next; </span><br><span class="line">        slow = slow.next; </span><br><span class="line">        <span class="keyword">if</span> (fast == slow) </span><br><span class="line">            <span class="keyword">break</span>; </span><br><span class="line">    &#125;<span class="comment">// 上⾯的代码类似 hasCycle 函数</span></span><br><span class="line">    	slow = head; </span><br><span class="line">    <span class="keyword">while</span> (slow != fast) &#123; </span><br><span class="line">        fast = fast.next; </span><br><span class="line">        slow = slow.next; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> slow; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="寻找链表的中点"><a href="#寻找链表的中点" class="headerlink" title="寻找链表的中点"></a>寻找链表的中点</h3><p>类似上⾯的思路，我们还可以让快指针⼀次前进两步，慢指针⼀次前进⼀ 步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。当链表的⻓度是奇数时，slow 恰巧停在中点位置；如果⻓度是偶数，slow 最终的位置是中间偏右。</p>
<p>寻找链表中点的⼀个重要作⽤是对链表进⾏归并排序。 回想数组的归并排序：求中点索引递归地把数组⼆分，最后合并两个有序数 组。对于链表，合并两个有序链表是很简单的，难点就在于⼆分。 但是现在你学会了找到链表的中点，就能实现链表的⼆分了。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">while</span> (fast != null &amp;&amp; fast.next != null) &#123; </span><br><span class="line">    fast = fast.next.next;</span><br><span class="line">    slow = slow.next; </span><br><span class="line">&#125;<span class="comment">// slow 就在中间位置 </span></span><br><span class="line"><span class="keyword">return</span> slow;</span><br></pre></td></tr></table></figure>

<h3 id="寻找链表的倒数第k个元素"><a href="#寻找链表的倒数第k个元素" class="headerlink" title="寻找链表的倒数第k个元素"></a>寻找链表的倒数第k个元素</h3><p>我们的思路还是使⽤快慢指针，让快指针先⾛ k 步，然后快慢指针开始同速 前进。这样当快指针⾛到链表末尾 null 时，慢指针所在的位置就是倒数第 k 个链表节点。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">ListNode slow, fast; </span><br><span class="line">slow = fast = head; </span><br><span class="line"><span class="keyword">while</span> (k-- &gt; <span class="number">0</span>) </span><br><span class="line">    fast = fast.next; </span><br><span class="line"><span class="keyword">while</span> (fast != null) &#123; </span><br><span class="line">    slow = slow.next; </span><br><span class="line">    fast = fast.next; &#125;</span><br><span class="line"><span class="keyword">return</span> slow;</span><br></pre></td></tr></table></figure>

<h2 id=""><a href="#" class="headerlink" title=""></a></h2><h2 id="左右指针的常见用法"><a href="#左右指针的常见用法" class="headerlink" title="左右指针的常见用法"></a>左右指针的常见用法</h2><p>左右指针在数组中实际是指两个索引值，⼀般初始化为 left = 0, right = nums.length - 1 。 </p>
<h3 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">int</span> right = nums.length - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right) &#123; </span><br><span class="line">        <span class="keyword">int</span> mid = (right + left) / <span class="number">2</span>; </span><br><span class="line">        <span class="keyword">if</span>(nums[mid] == target) </span><br><span class="line">            <span class="keyword">return</span> mid; </span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; target) </span><br><span class="line">            left = mid + <span class="number">1</span>; </span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &gt; target) </span><br><span class="line">            right = mid - <span class="number">1</span>; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="二数之和"><a href="#二数之和" class="headerlink" title="二数之和"></a>二数之和</h3><p>给定一个已经按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回两个下标值index1和index2。</p>
<p>只要数组有序就应该想到双指针用法，解法类似于二分查找，通过调节left和right来调整sum的大小。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = nums.length - <span class="number">1</span>; </span><br><span class="line">    <span class="keyword">while</span> (left &lt; right) &#123; </span><br><span class="line">        <span class="keyword">int</span> sum = nums[left] + nums[right]; </span><br><span class="line">        <span class="keyword">if</span> (sum == target) &#123; <span class="comment">// 题⽬要求的索引是从 1 开始的</span></span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;left + <span class="number">1</span>, right + <span class="number">1</span>&#125;; </span><br><span class="line">        &#125; </span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (sum &lt; target) &#123; </span><br><span class="line">            left++; </span><br><span class="line">            <span class="comment">// 让 sum ⼤⼀点 </span></span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (sum &gt; target) &#123; </span><br><span class="line">            right--; </span><br><span class="line">            <span class="comment">// 让 sum ⼩⼀点 </span></span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;<span class="number">-1</span>, <span class="number">-1</span>&#125;; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="反转数组"><a href="#反转数组" class="headerlink" title="反转数组"></a>反转数组</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">reverse</span><span class="params">(<span class="keyword">int</span>[] nums)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">int</span> right = nums.length - <span class="number">1</span>; </span><br><span class="line">    <span class="keyword">while</span> (left &lt; right) &#123; </span><br><span class="line">        <span class="comment">// swap(nums[left], nums[right]) </span></span><br><span class="line">        <span class="keyword">int</span> temp = nums[left]; </span><br><span class="line">        nums[left] = nums[right]; </span><br><span class="line">        nums[right] = temp; </span><br><span class="line">        left++; </span><br><span class="line">        right--; </span><br><span class="line">    &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="滑动窗口算法"><a href="#滑动窗口算法" class="headerlink" title="滑动窗口算法"></a>滑动窗口算法</h2><p>滑动窗口是双指针技巧的最高境界，可以解决一大类子字符串匹配的问题，比如：最小覆盖子串、字符串的排列、找到字符串中所有字母异位词、无重复字符的最长子串。其实算法的技巧思路特别简单，即维护一个窗口，不断滑动并更新答案。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">    <span class="comment">// 增⼤窗⼝ </span></span><br><span class="line">    window.add(s[right]); </span><br><span class="line">    right++; </span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span> (window needs shrink) &#123; </span><br><span class="line">        <span class="comment">// 缩⼩窗⼝ </span></span><br><span class="line">        window.<span class="built_in">remove</span>(s[left]); </span><br><span class="line">        left++; </span><br><span class="line">    &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这个算法技巧的时间复杂度是 O(N)，⽐字符串暴⼒算法要⾼效得多。 其实困扰⼤家的，不是算法的思路，⽽是各种细节问题。⽐如说如何向窗⼝ 中添加新元素，如何缩⼩窗⼝，在窗⼝滑动的哪个阶段更新结果。即便你明 ⽩了这些细节，也容易出 bug，找 bug 还不知道怎么找，真的挺让⼈⼼烦 的。</p>
<p><strong>所以今天我就写⼀套滑动窗⼝算法的代码框架，我连再哪⾥做输出</strong> <strong>debug</strong> <strong>都给你写好了，以后遇到相关的问题，你就默写出来如下框架然后改三个地</strong> <strong>⽅就⾏，还不会出</strong> <strong>bug</strong>： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/* 滑动窗口算法框架 */</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">slidingWindow</span><span class="params">(<span class="built_in">string</span> s, <span class="built_in">string</span> t)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; need, window;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">char</span> c : t) need[c]++;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> valid = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">        <span class="comment">// c 是将移入窗口的字符</span></span><br><span class="line">        <span class="keyword">char</span> c = s[right];</span><br><span class="line">        <span class="comment">// 右移窗口</span></span><br><span class="line">        right++;</span><br><span class="line">        <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">        ...</span><br><span class="line"></span><br><span class="line">        <span class="comment">/*** debug 输出的位置 ***/</span></span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">"window: [%d, %d)\n"</span>, left, right);</span><br><span class="line">        <span class="comment">/********************/</span></span><br><span class="line"></span><br><span class="line">        <span class="comment">// 判断左侧窗口是否要收缩</span></span><br><span class="line">        <span class="keyword">while</span> (window needs shrink) &#123;</span><br><span class="line">            <span class="comment">// d 是将移出窗口的字符</span></span><br><span class="line">            <span class="keyword">char</span> d = s[left];</span><br><span class="line">            <span class="comment">// 左移窗口</span></span><br><span class="line">            left++;</span><br><span class="line">            <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">            ...</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>而且，这两个<code>...</code>处的操作分别是右移和左移窗口更新操作，等会你会发现它们操作是完全对称的。本文代码为 C++ 实现，不会用到什么编程方面的奇技淫巧，但是还是简单介绍一下一些用到的数据结构，以免有的读者因为语言的细节问题阻碍对算法思想的理解：</p>
<p><code>unordered_map</code>就是哈希表（字典），它的一个方法<code>count(key)</code>相当于 Java 的<code>containsKey(key)</code>可以判断键 key 是否存在。可以使用方括号访问键对应的值<code>map[key]</code>。需要注意的是，如果该<code>key</code>不存在，C++ 会自动创建这个 key，并把<code>map[key]</code>赋值为 0。所以代码中多次出现的<code>map[key]++</code>相当于 Java 的<code>map.put(key, map.getOrDefault(key, 0) + 1)</code>。</p>
<h3 id="最小覆盖子串"><a href="#最小覆盖子串" class="headerlink" title="最小覆盖子串"></a>最小覆盖子串</h3><p>题目：给你一个字符串S、字符串T，请在字符串S中找出：包含T所有字母的最小子串。</p>
<p>就是说要在<code>S</code>(source) 中找到包含<code>T</code>(target) 中全部字母的一个子串，且这个子串一定是所有可能子串中最短的。</p>
<p>如果我们使用暴力解法，代码大概是这样的：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s.<span class="built_in">size</span>(); i++)</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; s.<span class="built_in">size</span>(); j++)</span><br><span class="line">        <span class="keyword">if</span> s[i:j] 包含 t 的所有字母:</span><br><span class="line">            更新答案</span><br></pre></td></tr></table></figure>

<p>而滑动窗口的思路是这样的：</p>
<p><em><strong>1、</strong></em>我们在字符串<code>S</code>中使用双指针中的左右指针技巧，初始化<code>left = right = 0</code>，把索引左闭右开区间<code>[left, right)</code>称为一个「窗口」。</p>
<p><em><strong>2、</strong></em>我们先不断地增加<code>right</code>指针扩大窗口<code>[left, right)</code>，直到窗口中的字符串符合要求（包含了<code>T</code>中的所有字符）。</p>
<p><em><strong>3、</strong></em>此时，我们停止增加<code>right</code>，转而不断增加<code>left</code>指针缩小窗口<code>[left, right)</code>，直到窗口中的字符串不再符合要求（不包含<code>T</code>中的所有字符了）。同时，每次增加<code>left</code>，我们都要更新一轮结果。</p>
<p><em><strong>4、</strong></em>重复第 2 和第 3 步，直到<code>right</code>到达字符串<code>S</code>的尽头</p>
<p>这个思路其实也不难，<strong>第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，</strong>也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。下面画图理解一下，<code>needs</code>和<code>window</code>相当于计数器，分别记录<code>T</code>中字符出现次数和「窗口」中的相应字符的出现次数。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//首先，初始化window和need两个哈希表，记录窗口中的字符和需要凑齐的字符：</span></span><br><span class="line"><span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; need, window;</span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">char</span> c : t) need[c]++;<span class="comment">//为每个键值赋值</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//然后，使用left和right变量初始化窗口的两端，不要忘了，区间[left, right)是左闭右开的，所以初始情况下窗口没有包含任何元素：</span></span><br><span class="line"><span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">int</span> valid = <span class="number">0</span>; </span><br><span class="line"><span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">    <span class="comment">// 开始滑动</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//其中valid变量表示窗口中满足need条件的字符个数，如果valid和need.size的大小相同，则说明窗口已满足条件，已经完全覆盖了串T。</span></span><br><span class="line"><span class="comment">//现在开始套模板，只需要思考以下四个问题：</span></span><br><span class="line"><span class="comment">//1、当移动right扩大窗口，即加入字符时，应该更新哪些数据？</span></span><br><span class="line"><span class="comment">//2、什么条件下，窗口应该暂停扩大，开始移动left缩小窗口？</span></span><br><span class="line"><span class="comment">//3、当移动left缩小窗口，即移出字符时，应该更新哪些数据？</span></span><br><span class="line"><span class="comment">//4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//如果一个字符进入窗口，应该增加window计数器；如果一个字符将移出窗口的时候，应该减少window计数器；当valid满足need时应该收缩窗口；应该在收缩窗口的时候更新最终结果。</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="built_in">string</span> <span class="title">minWindow</span><span class="params">(<span class="built_in">string</span> s, <span class="built_in">string</span> t)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; need, window;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">char</span> c : t) need[c]++;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> valid = <span class="number">0</span>;</span><br><span class="line">    <span class="comment">// 记录最小覆盖子串的起始索引及长度</span></span><br><span class="line">    <span class="keyword">int</span> start = <span class="number">0</span>, len = INT_MAX;</span><br><span class="line">    <span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">        <span class="comment">// c 是将移入窗口的字符</span></span><br><span class="line">        <span class="keyword">char</span> c = s[right];</span><br><span class="line">        <span class="comment">// 右移窗口</span></span><br><span class="line">        right++;</span><br><span class="line">        <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">        <span class="keyword">if</span> (need.count(c)) &#123;</span><br><span class="line">            window[c]++;</span><br><span class="line">            <span class="keyword">if</span> (window[c] == need[c])</span><br><span class="line">                valid++;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 判断左侧窗口是否要收缩</span></span><br><span class="line">        <span class="keyword">while</span> (valid == need.<span class="built_in">size</span>()) &#123;</span><br><span class="line">            <span class="comment">// 在这里更新最小覆盖子串</span></span><br><span class="line">            <span class="keyword">if</span> (right - left &lt; len) &#123;</span><br><span class="line">                start = left;</span><br><span class="line">                len = right - left;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// d 是将移出窗口的字符</span></span><br><span class="line">            <span class="keyword">char</span> d = s[left];</span><br><span class="line">            <span class="comment">// 左移窗口</span></span><br><span class="line">            left++;</span><br><span class="line">            <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">            <span class="keyword">if</span> (need.count(d)) &#123;</span><br><span class="line">                <span class="keyword">if</span> (window[d] == need[d])</span><br><span class="line">                    valid--;</span><br><span class="line">                window[d]--;</span><br><span class="line">            &#125;                    </span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 返回最小覆盖子串</span></span><br><span class="line">    <span class="keyword">return</span> len == INT_MAX ?</span><br><span class="line">        <span class="string">""</span> : s.substr(start, len);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>需要注意的是，当我们发现某个字符在<code>window</code>的数量满足了<code>need</code>的需要，就要更新<code>valid</code>，表示有一个字符已经满足要求。而且，你能发现，两次对窗口内数据的更新操作是完全对称的。</p>
<p>当<code>valid == need.size()</code>时，说明<code>T</code>中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。移动<code>left</code>收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。</p>
<p>至此，应该可以完全理解这套框架了，滑动窗口算法又不难，就是细节问题让人烦得很。<strong>以后遇到滑动窗口算法，你就按照这框架写代码，保准没有 bug，还省事儿</strong>。</p>
<h3 id="字符串排列"><a href="#字符串排列" class="headerlink" title="字符串排列"></a>字符串排列</h3><p>题目：给定两个字符串S1、S2，写一个函数来判断S2是否包含S1的序列；即第一个字符串的排列之一是第二个字符串的子串</p>
<p>这种题目，是明显的滑动窗口算法，<strong>相当给你一个<code>S</code>和一个<code>T</code>，请问你<code>S</code>中是否存在一个子串，包含<code>T</code>中所有字符且不包含其他字符</strong>？首先，先复制粘贴之前的算法框架代码，然后明确刚才提出的 4 个问题，即可写出这道题的答案：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 判断 s 中是否存在 t 的排列</span></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">checkInclusion</span><span class="params">(<span class="built_in">string</span> t, <span class="built_in">string</span> s)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; need, window;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">char</span> c : t) need[c]++;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> valid = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">        <span class="keyword">char</span> c = s[right];</span><br><span class="line">        right++;</span><br><span class="line">        <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">        <span class="keyword">if</span> (need.count(c)) &#123;</span><br><span class="line">            window[c]++;</span><br><span class="line">            <span class="keyword">if</span> (window[c] == need[c])</span><br><span class="line">                valid++;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// 判断左侧窗口是否要收缩</span></span><br><span class="line">        <span class="keyword">while</span> (right - left &gt;= t.<span class="built_in">size</span>()) &#123;</span><br><span class="line">            <span class="comment">// 在这里判断是否找到了合法的子串</span></span><br><span class="line">            <span class="keyword">if</span> (valid == need.<span class="built_in">size</span>())</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            <span class="keyword">char</span> d = s[left];</span><br><span class="line">            left++;</span><br><span class="line">            <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">            <span class="keyword">if</span> (need.count(d)) &#123;</span><br><span class="line">                <span class="keyword">if</span> (window[d] == need[d])</span><br><span class="line">                    valid--;</span><br><span class="line">                window[d]--;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 未找到符合条件的子串</span></span><br><span class="line">    <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>对于这道题的解法代码，基本上和最小覆盖子串一模一样，只需要改变两个地方：</p>
<p><strong>1、</strong>本题移动<code>left</code>缩小窗口的时机是窗口大小大于<code>t.size()</code>时，因为排列嘛，显然长度应该是一样的。</p>
<p><strong>2、</strong>当发现<code>valid == need.size()</code>时，就说明窗口中就是一个合法的排列，所以立即返回<code>true</code>。</p>
<p>至于如何处理窗口的扩大和缩小，和最小覆盖子串完全相同。</p>
<h3 id="找所有字母异位词"><a href="#找所有字母异位词" class="headerlink" title="找所有字母异位词"></a>找所有字母异位词</h3><p>给定一个字符串s和非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。（字母异位词指字母相同，但排列不同的字符串；不考虑答案输出的顺序）</p>
<p>呵呵，这个所谓的字母异位词，不就是排列吗，搞个高端的说法就能糊弄人了吗？<strong>相当于，输入一个串<code>S</code>，一个串<code>T</code>，找到<code>S</code>中所有<code>T</code>的排列，返回它们的起始索引</strong>。直接默写一下框架，明确刚才讲的 4 个问题，即可秒杀这道题：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">findAnagrams</span><span class="params">(<span class="built_in">string</span> s, <span class="built_in">string</span> t)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; need, window;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">char</span> c : t) need[c]++;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> valid = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; res; <span class="comment">// 记录结果</span></span><br><span class="line">    <span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">        <span class="keyword">char</span> c = s[right];</span><br><span class="line">        right++;</span><br><span class="line">        <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">        <span class="keyword">if</span> (need.count(c)) &#123;</span><br><span class="line">            window[c]++;</span><br><span class="line">            <span class="keyword">if</span> (window[c] == need[c]) </span><br><span class="line">                valid++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 判断左侧窗口是否要收缩</span></span><br><span class="line">        <span class="keyword">while</span> (right - left &gt;= t.<span class="built_in">size</span>()) &#123;</span><br><span class="line">            <span class="comment">// 当窗口符合条件时，把起始索引加入 res</span></span><br><span class="line">            <span class="keyword">if</span> (valid == need.<span class="built_in">size</span>())</span><br><span class="line">                res.push_back(left);</span><br><span class="line">            <span class="keyword">char</span> d = s[left];</span><br><span class="line">            left++;</span><br><span class="line">            <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">            <span class="keyword">if</span> (need.count(d)) &#123;</span><br><span class="line">                <span class="keyword">if</span> (window[d] == need[d])</span><br><span class="line">                    valid--;</span><br><span class="line">                window[d]--;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>跟寻找字符串的排列一样，只是找到一个合法异位词（排列）之后将起始索引加入<code>res</code>即可</p>
<h3 id="最长无重复子串"><a href="#最长无重复子串" class="headerlink" title="最长无重复子串"></a>最长无重复子串</h3><p>题目：给定一个字符串，找出其中不含有重复重复字符的的最长子串的长度。 </p>
<p>这个题终于有了点新意，不是一套框架就出答案，不过反而更简单了，稍微改一改框架就行了：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">lengthOfLongestSubstring</span><span class="params">(<span class="built_in">string</span> s)</span> </span>&#123;</span><br><span class="line">    <span class="built_in">unordered_map</span>&lt;<span class="keyword">char</span>, <span class="keyword">int</span>&gt; window;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> res = <span class="number">0</span>; <span class="comment">// 记录结果</span></span><br><span class="line">    <span class="keyword">while</span> (right &lt; s.<span class="built_in">size</span>()) &#123;</span><br><span class="line">        <span class="keyword">char</span> c = s[right];</span><br><span class="line">        right++;</span><br><span class="line">        <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">        window[c]++;</span><br><span class="line">        <span class="comment">// 判断左侧窗口是否要收缩</span></span><br><span class="line">        <span class="keyword">while</span> (window[c] &gt; <span class="number">1</span>) &#123;</span><br><span class="line">            <span class="keyword">char</span> d = s[left];</span><br><span class="line">            left++;</span><br><span class="line">            <span class="comment">// 进行窗口内数据的一系列更新</span></span><br><span class="line">            window[d]--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 在这里更新答案</span></span><br><span class="line">        res = <span class="built_in">max</span>(res, right - left);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这就是变简单了，连<code>need</code>和<code>valid</code>都不需要，而且更新窗口内数据也只需要简单的更新计数器<code>window</code>即可。</p>
<p>当<code>window[c]</code>值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动<code>left</code>缩小窗口了嘛。唯一需要注意的是，在哪里更新结果<code>res</code>呢？我们要的是最长无重复子串，哪一个阶段可以保证窗口中的字符串是没有重复的呢？</p>
<p>这里和之前不一样，**要在收缩窗口完成后更新<code>res</code>**，因为窗口收缩的 while 条件是存在重复元素，换句话说收缩完成后一定保证窗口中没有重复嘛。</p>
<h1 id="twoSum问题的核心思想"><a href="#twoSum问题的核心思想" class="headerlink" title="twoSum问题的核心思想"></a>twoSum问题的核心思想</h1><h2 id="第一题"><a href="#第一题" class="headerlink" title="第一题"></a>第一题</h2><p>这个问题的<strong>最基本形式</strong>是这样：给你⼀个数组和⼀个整数 target ，可以保 证数组中<strong>存在</strong>两个数的和为 target ，请你返回这两个数的索引。这个问题如何解决呢？⾸先最简单粗暴的办法当然是穷举了：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123; </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; nums.length; i++) </span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = i + <span class="number">1</span>; j &lt; nums.length; j++) </span><br><span class="line">            <span class="keyword">if</span> (nums[j] == target - nums[i]) </span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123; i, j &#125;; </span><br><span class="line">    <span class="comment">// 不存在这么两个数 </span></span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123;<span class="number">-1</span>, <span class="number">-1</span>&#125;; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这个解法⾮常直接，时间复杂度 O(N^2)，空间复杂度 O(1)。 可以通过⼀个哈希表减少时间复杂度：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123; </span><br><span class="line">    <span class="keyword">int</span> n = nums.length; </span><br><span class="line">    index&lt;Integer, Integer&gt; </span><br><span class="line">        index = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="comment">// 构造⼀个哈希表：元素映射到相应的索引 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) </span><br><span class="line">        index.<span class="built_in">put</span>(nums[i], i); </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123; </span><br><span class="line">        <span class="keyword">int</span> other = target - nums[i]; </span><br><span class="line">        <span class="comment">// 如果 other 存在且不是 nums[i] 本⾝ </span></span><br><span class="line">        <span class="keyword">if</span> (index.containsKey(other) &amp;&amp; index.<span class="built_in">get</span>(other) != i) </span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123;i, index.<span class="built_in">get</span>(other)&#125;; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[] &#123;<span class="number">-1</span>, <span class="number">-1</span>&#125;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这样，由于哈希表的查询时间为 O(1)，算法的时间复杂度降低到 O(N)，但 是需要 O(N) 的空间复杂度来存储哈希表。不过综合来看，是要⽐暴⼒解法 ⾼效的。 </p>
<p><strong>我觉得</strong> <strong>Two Sum</strong> <strong>系列问题就是想教我们如何使⽤哈希表处理问题</strong>。我们接 着往后看。 </p>
<h2 id="第二题"><a href="#第二题" class="headerlink" title="第二题"></a>第二题</h2><p>这⾥我们稍微修改⼀下上⾯的问题。我们设计⼀个类，拥有两个 API： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">TwoSum</span> &#123;</span> </span><br><span class="line">    <span class="comment">// 向数据结构中添加⼀个数 number </span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> number)</span></span>; </span><br><span class="line">    <span class="comment">// 寻找当前数据结构中是否存在两个数的和为 value </span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> value)</span></span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如何实现这两个 API 呢，我们可以仿照上⼀道题⽬，使⽤⼀个哈希表辅助 find ⽅法：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">TwoSum</span> &#123;</span> </span><br><span class="line">    Map&lt;Integer, Integer&gt; freq = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> number)</span> </span>&#123; </span><br><span class="line">        <span class="comment">// 记录 number 出现的次数 </span></span><br><span class="line">        freq.<span class="built_in">put</span>(number, freq.getOrDefault(number, <span class="number">0</span>) + <span class="number">1</span>); </span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123; </span><br><span class="line">        <span class="keyword">for</span> (Integer key : freq.keySet()) &#123; </span><br><span class="line">            <span class="keyword">int</span> other = value - key; </span><br><span class="line">            <span class="comment">// 情况⼀ </span></span><br><span class="line">            <span class="keyword">if</span> (other == key &amp;&amp; freq.<span class="built_in">get</span>(key) &gt; <span class="number">1</span>) </span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">            <span class="comment">// 情况⼆ </span></span><br><span class="line">            <span class="keyword">if</span> (other != key &amp;&amp; freq.containsKey(other)) </span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>; </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>; </span><br><span class="line">    &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>进⾏ find 的时候有两种情况，举个例⼦： </p>
<p>情况⼀： add 了 [3,3,2,5] 之后，执⾏ find(6) ，由于 3 出现了两次，3 + 3 = 6，所以返回 true。 </p>
<p>情况⼆： add 了 [3,3,2,5] 之后，执⾏ find(7) ，那么 key 为 2， other 为 5 时算法可以返回 true。 </p>
<p>除了上述两种情况外， find 只能返回 false 了。 </p>
<p>对于这个解法的时间复杂度呢， add ⽅法是 O(1)， find ⽅法是 O(N)，空 间复杂度为 O(N)，和上⼀道题⽬⽐较类似。<strong>但是对于</strong> <strong>API</strong> <strong>的设计，是需要考虑现实情况的</strong>。⽐如说，我们设计的这个 类，使⽤ find ⽅法⾮常频繁，那么每次都要 O(N) 的时间，岂不是很浪费 费时间吗？对于这种情况，我们是否可以做些优化呢？ </p>
<p>是的，对于频繁使⽤ find ⽅法的场景，我们可以进⾏优化。我们可以参 考上⼀道题⽬的暴⼒解法，借助<strong>哈希集合</strong>来针对性优化 find ⽅法：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">TwoSum</span> &#123;</span></span><br><span class="line">    Set&lt;Integer&gt; sum = <span class="keyword">new</span> HashSet&lt;&gt;(); </span><br><span class="line">    List&lt;Integer&gt; nums = <span class="keyword">new</span> ArrayList&lt;&gt;(); </span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> number)</span> </span>&#123; </span><br><span class="line">        <span class="comment">// 记录所有可能组成的和 </span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> n : nums) </span><br><span class="line">            sum.add(n + number); </span><br><span class="line">        nums.add(number); </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123; </span><br><span class="line">        <span class="keyword">return</span> sum.contains(value); </span><br><span class="line">    &#125; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这样 sum 中就储存了所有加⼊数字可能组成的和，每次 find 只要花费 O(1) 的时间在集合中判断⼀下是否存在就⾏了，显然⾮常适合频繁使⽤ find 的场景。</p>
<p>对于 TwoSum 问题，⼀个难点就是给的数组<strong>⽆序</strong>。对于⼀个⽆序的数组， 我们似乎什么技巧也没有，只能暴⼒穷举所有可能。 </p>
<p><strong>⼀般情况下，我们会⾸先把数组排序再考虑双指针技巧</strong>。TwoSum 启发我 们，HashMap 或者 HashSet 也可以帮助我们处理⽆序数组相关的简单问题。 另外，设计的核⼼在于权衡，利⽤不同的数据结构，可以得到⼀些针对性的 加强。 </p>
<p>最后，如果 TwoSum I 中给的数组是有序的，应该如何编写算法呢？答案很 简单，前⽂「双指针技巧汇总」写过：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span>[] twoSum(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target) &#123; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = nums.length - <span class="number">1</span>; </span><br><span class="line">    <span class="keyword">while</span> (left &lt; right) &#123; </span><br><span class="line">        <span class="keyword">int</span> sum = nums[left] + nums[right]; </span><br><span class="line">        <span class="keyword">if</span> (sum == target) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;left, right&#125;; </span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (sum &lt; target) &#123; </span><br><span class="line">            left++; <span class="comment">// 让 sum ⼤⼀点 </span></span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (sum &gt; target) &#123; </span><br><span class="line">            right--; <span class="comment">// 让 sum ⼩⼀点 </span></span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 不存在这样两个数 </span></span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">new</span> <span class="keyword">int</span>[]&#123;<span class="number">-1</span>, <span class="number">-1</span>&#125;; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="二分查找详解"><a href="#二分查找详解" class="headerlink" title="二分查找详解"></a>二分查找详解</h1><p>⼆分查找并不简单，Knuth ⼤佬（发明 KMP 算法的那位）都说⼆分查找： </p>
<p><strong>思路很简单，细节是魔⿁</strong>。很多⼈喜欢拿整型溢出的 bug 说事⼉，但是⼆分 查找真正的坑根本就不是那个细节问题，⽽是在于到底要给 mid 加⼀还是 减⼀，while ⾥到底⽤ &lt;= 还是 &lt; 。 </p>
<h2 id="二分搜索诗"><a href="#二分搜索诗" class="headerlink" title="二分搜索诗"></a>二分搜索诗</h2><p>管他左侧还右侧，搜索区间定乾坤。</p>
<p>搜索一个元素时，搜索区间两端闭。</p>
<p>while条件带等号，否则需要打补丁。</p>
<p>if相等就返回，其他的事甭操心。</p>
<p>mid必须加减一，因为区间两端闭。</p>
<p>while结束就凉凉，凄凄惨惨返-1。</p>
<p>搜索左右边界时，搜索区间要阐明。</p>
<p>左闭右开最常见，其余逻辑便自明。</p>
<p>while要用小于号，这样才能不漏掉。</p>
<p>if相等别返回，利用mid锁边界。</p>
<p>mid加一或减一？要看区间区间开或闭。</p>
<p>while结束不算完，因为你还没返回。</p>
<p>索引可能出边界，if检查保平安。</p>
<h2 id="二分查找框架"><a href="#二分查找框架" class="headerlink" title="二分查找框架"></a>二分查找框架</h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = ...; </span><br><span class="line">    <span class="keyword">while</span>(...) &#123; </span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left) / <span class="number">2</span>; </span><br><span class="line">        <span class="keyword">if</span> (nums[mid] == target) &#123; </span><br><span class="line">            ... </span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; target) &#123; </span><br><span class="line">            left = ... </span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &gt; target) &#123; </span><br><span class="line">            right = ... </span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ...; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>分析⼆分查找的⼀个技巧是：不要出现</strong> <strong>else****，⽽是把所有情况⽤</strong> <strong>else if</strong> <strong>写清</strong> <strong>楚，这样可以清楚地展现所有细节</strong>。本⽂都会使⽤ else if，旨在讲清楚。</p>
<p>其中 … 标记的部分，就是可能出现细节问题的地⽅，当你⻅到⼀个⼆分 查找的代码时，⾸先注意这⼏个地⽅。后⽂⽤实例分析这些地⽅能有什么样 的变化。 </p>
<p>另外声明⼀下，计算 mid 时需要防⽌溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防⽌了 left 和right 太⼤直接相加导致溢出</p>
<h2 id="寻找一个数：基本二分查找"><a href="#寻找一个数：基本二分查找" class="headerlink" title="寻找一个数：基本二分查找"></a>寻找一个数：基本二分查找</h2><p>这个场景是最简单的，肯能也是⼤家最熟悉的，即搜索⼀个数，如果存在， 返回其索引，否则返回 -1。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> right = nums.length - <span class="number">1</span>; <span class="comment">// 注意 </span></span><br><span class="line">    <span class="keyword">while</span>(left &lt;= right) &#123; </span><br><span class="line">        <span class="keyword">int</span> mid = left + (right - left) / <span class="number">2</span>; </span><br><span class="line">        <span class="keyword">if</span>(nums[mid] == target) </span><br><span class="line">            <span class="keyword">return</span> mid; </span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; target) </span><br><span class="line">            left = mid + <span class="number">1</span>; <span class="comment">// 注意 </span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &gt; target) </span><br><span class="line">            right = mid - <span class="number">1</span>; <span class="comment">// 注意 </span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>1****、为什么</strong> <strong>while</strong> <strong>循环的条件中是</strong> **&lt;=**<strong>，⽽不是</strong> **&lt;**？ </p>
<p>答：因为初始化 right 的赋值是 nums.length - 1 ，即最后⼀个元素的索 引，⽽不是 nums.length 。 </p>
<p>这⼆者可能出现在不同功能的⼆分查找中，区别是：前者相当于两端都闭区 间 [left, right] ，后者相当于左闭右开区间 [left, right) ，因为索引⼤⼩为 nums.length 是越界的。</p>
<p>我们这个算法中使⽤的是前者 [left, right] 两端都闭的区间。<strong>这个区间</strong> </p>
<p><strong>其实就是每次进⾏搜索的区间</strong>。 </p>
<p>2、什么时候应该停⽌搜索呢？</p>
<p>当然，找到了⽬标值的时候可以终⽌： </p>
<p>if(nums[mid] == target) return mid; </p>
<p>但如果没找到，就需要 while 循环终⽌，然后返回 -1。那 while 循环什么时 候应该终⽌？<strong>搜索区间为空的时候应该终⽌</strong>，意味着你没得找了，就等于没 找到嘛。 </p>
<p>while(left &lt;= right) 的终⽌条件是 left == right + 1 ，写成区间的形式 就是 [right + 1, right] ，或者带个具体的数字进去 [3, 2] ，可⻅<strong>这时候</strong> <strong>区间为空</strong>，</p>
<p>while(left &lt; right) 的终⽌条件是 left == right ，写成区间的形式就是 [left, right] ，或者带个具体的数字进去 [2, 2] ，<strong>这时候区间⾮空</strong>，还 有⼀个数 2，但此时 while 循环终⽌了。也就是说这区间 [2, 2] 被漏掉 了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。</p>
<p><strong>3****、为什么</strong> <strong>left = mid + 1</strong> <strong>，</strong> <strong>right = mid - 1</strong> <strong>？我看有的代码是</strong> <strong>right =</strong> <strong>mid</strong> <strong>或者</strong> <strong>left = mid</strong> <strong>，没有这些加加减减，到底怎么回事，怎么判断</strong>？ </p>
<p>答：这也是⼆分查找的⼀个难点，不过只要你能理解前⾯的内容，就能够很 容易判断。 </p>
<p>刚才明确了「搜索区间」这个概念，⽽且本算法的搜索区间是两端都闭的， 即 [left, right] 。那么当我们发现索引 mid 不是要找的 target 时，下 ⼀步应该去搜索哪⾥呢？ 当然是去搜索 [left, mid-1] 或者 [mid+1, right] 对不对？<strong>因为</strong> <strong>mid</strong> <strong>已</strong> <strong>经搜索过，应该从搜索区间中去除</strong>。</p>
<p><strong>4****、此算法有什么缺陷</strong>？ </p>
<p>答：⾄此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但 是，这个算法存在局限性。 </p>
<p>⽐如说给你有序数组 nums = [1,2,2,2,3] ， target 为 2，此算法返回的索 引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我 想得到 target 的右侧边界，即索引 3，这样的话此算法是⽆法处理的。</p>
<h2 id="寻找左侧边界的⼆分搜索"><a href="#寻找左侧边界的⼆分搜索" class="headerlink" title="寻找左侧边界的⼆分搜索"></a><strong>寻找左侧边界的⼆分搜索</strong></h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">left_bound</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (nums.length == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">-1</span>; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">int</span> right = nums.length; <span class="comment">// 注意 </span></span><br><span class="line">    <span class="keyword">while</span> (left &lt; right) &#123; <span class="comment">// 注意 </span></span><br><span class="line">        <span class="keyword">int</span> mid = (left + right) / <span class="number">2</span>; </span><br><span class="line">        <span class="keyword">if</span> (nums[mid] == target) &#123; </span><br><span class="line">            right = mid; </span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; target) &#123; </span><br><span class="line">            left = mid + <span class="number">1</span>; </span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &gt; target) &#123; </span><br><span class="line">            right = mid; <span class="comment">// 注意 </span></span><br><span class="line">        &#125; </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> left; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>1****、为什么</strong> <strong>while</strong> <strong>中是</strong> <strong>&lt;</strong> <strong>⽽不是</strong> <strong>&lt;=</strong> ? </p>
<p>答：⽤相同的⽅法分析，因为 right = nums.length ⽽不是 nums.length - 1 。因此每次循环的「搜索区间」是 [left, right) 左闭右开。 while(left &lt; right) 终⽌的条件是 left == right ，此时搜索区间 [left, left) 为空，所以可以正确终⽌。 </p>
<h2 id="寻找右侧边界的⼆分查找"><a href="#寻找右侧边界的⼆分查找" class="headerlink" title="寻找右侧边界的⼆分查找"></a><strong>寻找右侧边界的⼆分查找</strong></h2><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">right_bound</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> target)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">if</span> (nums.length == <span class="number">0</span>) <span class="keyword">return</span> <span class="number">-1</span>; </span><br><span class="line">    <span class="keyword">int</span> left = <span class="number">0</span>, right = nums.length; </span><br><span class="line">    </span><br><span class="line">    <span class="keyword">while</span> (left &lt; right) &#123; </span><br><span class="line">        <span class="keyword">int</span> mid = (left + right) / <span class="number">2</span>; </span><br><span class="line">        <span class="keyword">if</span> (nums[mid] == target) &#123; </span><br><span class="line">            left = mid + <span class="number">1</span>; <span class="comment">// 注意 </span></span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &lt; target) &#123;</span><br><span class="line">            left = mid + <span class="number">1</span>; </span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (nums[mid] &gt; target) &#123; </span><br><span class="line">            right = mid; </span><br><span class="line">        &#125; </span><br><span class="line">    &#125;<span class="keyword">return</span> left - <span class="number">1</span>; <span class="comment">// 注意 </span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="字符串乘法"><a href="#字符串乘法" class="headerlink" title="字符串乘法"></a>字符串乘法</h1><p>对于⽐较⼩的数字，做运算可以直接使⽤编程语⾔提供的运算符，但是如果 相乘的两个因数⾮常⼤，语⾔提供的数据类型可能就会溢出。⼀种替代⽅案 就是，运算数以字符串的形式输⼊，然后模仿我们⼩学学习的乘法算术过程 计算出结果，并且也⽤字符串表⽰。</p>
<h2 id="题目"><a href="#题目" class="headerlink" title="题目"></a>题目</h2><p>给定两个以字符串形式表示的非负整数num1、num2，返回num1和num2的乘积，它们的乘积也表示为字符串的形式。</p>
<p>需要注意的是， num1 和 num2 可以⾮常⻓，所以不可以把他们直接转成 整型然后运算，唯⼀的思路就是模仿我们⼿算乘法。 </p>
<h2 id="思路"><a href="#思路" class="headerlink" title="思路"></a>思路</h2><p>计算 123 × 5 ，再计算 123 × 4 ，最后错⼀位相加。这个流程恐怕⼩学⽣ 都可以熟练完成，但是你是否能<strong>把这个运算过程进⼀步机械化</strong>，写成⼀套算 法指令让没有任何智商的计算机来执⾏呢？ </p>
<p>你看这个简单过程，其中涉及乘法进位，涉及错位相加，还涉及加法进位； ⽽且还有⼀些不易察觉的问题，⽐如说两位数乘以两位数，结果可能是四位 数，也可能是三位数，你怎么想出⼀个标准化的处理⽅式？这就是算法的魅 ⼒，如果没有计算机思维，简单的问题可能都没办法⾃动化处理。 </p>
<p>⾸先，我们这种⼿算⽅式还是太「⾼级」了，我们要再「低级」⼀点， 123 × 5 和 123 × 4 的过程还可以进⼀步分解，最后再相加： </p>
<p>现在 123 并不⼤，如果是个很⼤的数字的话，是⽆法直接计算乘积的。我 们可以⽤⼀个数组在底下接收相加结果： </p>
<p>整个计算过程⼤概是这样，<strong>有两个指针</strong> <strong>i</strong><em>，*<em>j</em></em> <strong>在</strong> <strong>num1</strong> <strong>和</strong> <strong>num2</strong> <strong>上游⾛，</strong> </p>
<p><strong>计算乘积，同时将乘积叠加到</strong> <strong>res</strong> <strong>的正确位置</strong>：  现在还有⼀个关键问题，如何将乘积叠加到 res 的正确位置，或者说，如 何通过 i，j 计算 res 的对应索引呢？ 其实，细⼼观察之后就发现， <strong>num1[i]</strong> <strong>和</strong> <strong>num2[j]</strong> <strong>的乘积对应的就是</strong> <strong>res[i+j]</strong> <strong>和</strong> <strong>res[i+j+1]</strong> <strong>这两个位置</strong>。 </p>
<p>明⽩了这⼀点，就可以⽤代码模仿出这个计算过程了：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="built_in">string</span> <span class="title">multiply</span><span class="params">(<span class="built_in">string</span> num1, <span class="built_in">string</span> num2)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> m = num1.<span class="built_in">size</span>(), n = num2.<span class="built_in">size</span>(); </span><br><span class="line">    <span class="comment">// 结果最多为 m + n 位数 </span></span><br><span class="line">    <span class="function"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; <span class="title">res</span><span class="params">(m + n, <span class="number">0</span>)</span></span>; </span><br><span class="line">    <span class="comment">// 从个位数开始逐位相乘 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = m - <span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) </span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = n - <span class="number">1</span>; j &gt;= <span class="number">0</span>; j--) &#123; </span><br><span class="line">            <span class="keyword">int</span> mul = (num1[i]-<span class="string">'0'</span>) * (num2[j]-<span class="string">'0'</span>); </span><br><span class="line">            <span class="comment">// 乘积在 res 对应的索引位置 </span></span><br><span class="line">            <span class="keyword">int</span> p1 = i + j, p2 = i + j + <span class="number">1</span>; </span><br><span class="line">            <span class="comment">// 叠加到 res 上 </span></span><br><span class="line">            <span class="keyword">int</span> sum = mul + res[p2]; </span><br><span class="line">            res[p2] = sum % <span class="number">10</span>; </span><br><span class="line">            res[p1] += sum / <span class="number">10</span>; </span><br><span class="line">        &#125; </span><br><span class="line">    <span class="comment">// 结果前缀可能存的 0（未使⽤的位） </span></span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">while</span> (i &lt; res.<span class="built_in">size</span>() &amp;&amp; res[i] == <span class="number">0</span>) </span><br><span class="line">        i++; </span><br><span class="line">    <span class="comment">// 将计算结果转化成字符串 </span></span><br><span class="line">    <span class="built_in">string</span> str; </span><br><span class="line">    <span class="keyword">for</span> (; i &lt; res.<span class="built_in">size</span>(); i++) </span><br><span class="line">        str.push_back(<span class="string">'0'</span> + res[i]); </span><br><span class="line">    <span class="keyword">return</span> str.<span class="built_in">size</span>() == <span class="number">0</span> ? <span class="string">"0"</span> : str; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>总结⼀下</strong>，我们习以为常的⼀些思维⽅式，在计算机看来是⾮常难以做到 的。⽐如说我们习惯的算术流程并不复杂，但是如果让你再进⼀步，翻译成 代码逻辑，并不简单。算法需要将计算流程再简化，通过边算边叠加的⽅式 来得到结果。 </p>
<p>俗话教育我们，不要陷⼊思维定式，不要程序化，要发散思维，要创新。但 我觉得程序化并不是坏事，可以⼤幅提⾼效率，减⼩失误率。算法不就是⼀ 套程序化的思维吗，只有程序化才能让计算机帮助我们解决复杂问题呀！</p>
<h1 id="前缀和技巧"><a href="#前缀和技巧" class="headerlink" title="前缀和技巧"></a>前缀和技巧</h1><h2 id="题目："><a href="#题目：" class="headerlink" title="题目："></a>题目：</h2><p>算出⼀共有⼏个和为 k 的⼦数组。给定一个整数数组和一个整数k，你需要找到该数组中和为k的连续的子数组的个数。</p>
<p>输入：nums = [1,1,1], k = 2；输出：2，[1,1]与[1,1]为两种不同的情况。</p>
<h2 id="解法思路："><a href="#解法思路：" class="headerlink" title="解法思路："></a>解法思路：</h2><p>那我把所有⼦数组都穷举出来，算它们的和，看看谁的和等于 k 不就⾏了。 关键是，<strong>如何快速得到某个⼦数组的和呢</strong>，⽐如说给你⼀个数组 nums ，让 你实现⼀个接⼝ sum(i, j) ，这个接⼝要返回 nums[i..j] 的和，⽽且会被 多次调⽤，你怎么实现这个接⼝呢？ </p>
<p>因为接⼝要被多次调⽤，显然不能每次都去遍历 nums[i..j] ，有没有⼀种 快速的⽅法在 O(1) 时间内算出 nums[i..j] 呢？这就需要<strong>前缀和</strong>技巧了。</p>
<h3 id="什么是前缀和"><a href="#什么是前缀和" class="headerlink" title="什么是前缀和"></a>什么是前缀和</h3><p>前缀和的思路是这样的，对于⼀个给定的数组 nums ，我们额外开辟⼀个前 缀和数组进⾏预处理：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> n = nums.length; <span class="comment">// 前缀和数组</span></span><br><span class="line"><span class="keyword">int</span>[] preSum = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>]; </span><br><span class="line">preSum[<span class="number">0</span>] = <span class="number">0</span>; </span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) </span><br><span class="line">    preSum[i + <span class="number">1</span>] = preSum[i] + nums[i];</span><br></pre></td></tr></table></figure>

<p>这个前缀和数组 preSum 的含义也很好理解， preSum[i] 就是 nums[0..i- 1] 的和。那么如果我们想求 nums[i..j] 的和，只需要⼀步操作 </p>
<p>preSum[j+1]-preSum[i] 即可，⽽不需要重新去遍历数组了。 </p>
<p>回到这个⼦数组问题，我们想求有多少个⼦数组的和为 k，借助前缀和技巧 </p>
<p>很容易写出⼀个解法： </p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">subarraySum</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> n = nums.length; </span><br><span class="line">    <span class="comment">// 构造前缀和 </span></span><br><span class="line">    <span class="keyword">int</span>[] sum = <span class="keyword">new</span> <span class="keyword">int</span>[n + <span class="number">1</span>]; </span><br><span class="line">    sum[<span class="number">0</span>] = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) </span><br><span class="line">        sum[i + <span class="number">1</span>] = sum[i] + nums[i]; </span><br><span class="line">    <span class="keyword">int</span> ans = <span class="number">0</span>; <span class="comment">// 穷举所有⼦数组 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) </span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; j++)</span><br><span class="line">            <span class="comment">// sum of nums[j..i-1] </span></span><br><span class="line">            <span class="keyword">if</span> (sum[i] - sum[j] == k) </span><br><span class="line">                ans++; </span><br><span class="line">    <span class="keyword">return</span> ans; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这个解法的时间复杂度 O(N^2) 空间复杂度 O(N) ，并不是最优的解法。不 过通过这个解法理解了前缀和数组的⼯作原理之后，可以使⽤⼀些巧妙的办 法把时间复杂度进⼀步降低</p>
<h3 id="优化解法"><a href="#优化解法" class="headerlink" title="优化解法"></a>优化解法</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//前⾯的解法有嵌套的 for 循环：</span></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; i; j++) </span><br><span class="line">        <span class="keyword">if</span> (sum[i] - sum[j] == k) </span><br><span class="line">            ans++;</span><br><span class="line"><span class="comment">//第⼆层 for 循环在⼲嘛呢？翻译⼀下就是，在计算，有⼏个 j 能够使得 sum[i] 和 sum[j] 的差为 k。毎找到⼀个这样的 j ，就把结果加⼀。 我们可以把 if 语句⾥的条件判断移项，这样写：</span></span><br><span class="line"><span class="keyword">if</span> (sum[j] == sum[i] - k) </span><br><span class="line">    ans++;</span><br><span class="line"><span class="comment">//优化的思路是：我直接记录下有⼏个 sum[j] 和 sum[i] - k 相等，直接更 新结果，就避免了内层的 for 循环。</span></span><br><span class="line"><span class="comment">//我们可以⽤哈希表，在记录前缀和的同 时记录该前缀和出现的次数。</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">subarraySum</span><span class="params">(<span class="keyword">int</span>[] nums, <span class="keyword">int</span> k)</span> </span>&#123; </span><br><span class="line">    <span class="keyword">int</span> n = nums.length; <span class="comment">// map：前缀和 -&gt; 该前缀和出现的次数 </span></span><br><span class="line">    HashMap&lt;Integer, Integer&gt;;</span><br><span class="line">    preSum = <span class="keyword">new</span> HashMap&lt;&gt;(); </span><br><span class="line">    <span class="comment">// base case </span></span><br><span class="line">    preSum.<span class="built_in">put</span>(<span class="number">0</span>, <span class="number">1</span>); </span><br><span class="line">    </span><br><span class="line">    <span class="keyword">int</span> ans = <span class="number">0</span>, sum0_i = <span class="number">0</span>; </span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; i++) &#123; </span><br><span class="line">        sum0_i += nums[i]; </span><br><span class="line">        <span class="comment">// 这是我们想找的前缀和 nums[0..j] </span></span><br><span class="line">        <span class="keyword">int</span> sum0_j = sum0_i - k; </span><br><span class="line">        <span class="comment">// 如果前⾯有这个前缀和，则直接更新答案 </span></span><br><span class="line">        <span class="keyword">if</span> (preSum.containsKey(sum0_j)) </span><br><span class="line">            ans += preSum.<span class="built_in">get</span>(sum0_j); </span><br><span class="line">        <span class="comment">// 把前缀和 nums[0..i] 加⼊并记录出现次数 </span></span><br><span class="line">        preSum.<span class="built_in">put</span>(sum0_i, preSum.getOrDefault(sum0_i, <span class="number">0</span>) + <span class="number">1</span>); </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> ans; </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>这样，就把时间复杂度降到了 O(N) ，是最优解法了。</p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p>前缀和不难，却很有⽤，主要⽤于处理数组区间的问题。 ⽐如说，让你统计班上同学考试成绩在不同分数段的百分⽐，也可以利⽤前 缀和技巧</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span>[] scores; <span class="comment">// 存储着所有同学的分数 </span></span><br><span class="line"><span class="comment">// 试卷满分 150 分 </span></span><br><span class="line"><span class="keyword">int</span>[] count = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">150</span> + <span class="number">1</span>] <span class="comment">// 记录每个分数有⼏个同学 </span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> score : scores)</span><br><span class="line">        count[score]++;</span><br><span class="line"><span class="comment">// 构造前缀和 </span></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; count.length; i++) </span><br><span class="line">    count[i] = count[i] + count[i<span class="number">-1</span>];</span><br></pre></td></tr></table></figure>

<p>这样，给你任何⼀个分数段，你都能通过前缀和相减快速计算出这个分数段 \的⼈数，百分⽐也就很容易计算了。 </p>
<p>但是，稍微复杂⼀些的算法问题，不⽌考察简单的前缀和技巧。⽐如本⽂探 讨的这道题⽬，就需要借助前缀和的思路做进⼀步的优化，借助哈希表去除 不必要的嵌套循环。可⻅对题⽬的理解和细节的分析能⼒对于算法的优化是 ⾄关重要的。 </p>

    </div>
    
    
    
    
    <div>
      
        <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束<i class="fa fa-paw"></i>感谢您的阅读-------------</div>
    
</div>

      
    </div>
        <div class="reward-container">
  <div>坚持原创技术分享，您的支持将鼓励我继续创作！</div>
  <button onclick="var qr = document.getElementById('qr'); qr.style.display = (qr.style.display === 'none') ? 'block' : 'none';">
    打赏
  </button>
  <div id="qr" style="display: none;">
      
      <div style="display: inline-block;">
        <img src="/images/alipay.png" alt="Li Yudong 支付宝">
        <p>支付宝</p>
      </div>

  </div>
</div>

        

<div>
<ul class="post-copyright">
  <li class="post-copyright-author">
    <strong>本文作者： </strong>Li Yudong
  </li>
  <li class="post-copyright-link">
    <strong>本文链接：</strong>
    <a href="http://example.com/2020/09/29/%E7%AE%97%E6%B3%95/%E5%8F%8C%E6%8C%87%E9%92%88%E6%9F%A5%E6%89%BE/" title="双指针查找与常用算法框架">http://example.com/2020/09/29/算法/双指针查找/</a>
  </li>
  <li class="post-copyright-license">
    <strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="noopener" target="_blank"><i class="fab fa-fw fa-creative-commons"></i>BY-NC-SA</a> 许可协议。转载请注明出处！
  </li>
</ul>
</div>

    
      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E7%AE%97%E6%B3%95%E6%A1%86%E6%9E%B6/" rel="tag"># 算法框架</a>
          </div>
    
        

    
        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2020/09/23/%E5%89%8D%E7%AB%AF/jQuery%E6%95%99%E7%A8%8B/" rel="prev" title="jQuery教程">
      <i class="fa fa-chevron-left"></i> jQuery教程
    </a></div>
      <div class="post-nav-item">
    <a href="/2020/10/08/%E7%AE%97%E6%B3%95/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95/" rel="next" title="数据结构算法">
      数据结构算法 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  



          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#双指针技巧详解"><span class="nav-number">1.</span> <span class="nav-text">双指针技巧详解</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#快慢指针的用法"><span class="nav-number">1.1.</span> <span class="nav-text">快慢指针的用法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#判定链表中是否有环"><span class="nav-number">1.1.1.</span> <span class="nav-text">判定链表中是否有环</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#已知链表中有环，返回其起始位置"><span class="nav-number">1.1.2.</span> <span class="nav-text">已知链表中有环，返回其起始位置</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#寻找链表的中点"><span class="nav-number">1.1.3.</span> <span class="nav-text">寻找链表的中点</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#寻找链表的倒数第k个元素"><span class="nav-number">1.1.4.</span> <span class="nav-text">寻找链表的倒数第k个元素</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#"><span class="nav-number">1.2.</span> <span class="nav-text"></span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#左右指针的常见用法"><span class="nav-number">1.3.</span> <span class="nav-text">左右指针的常见用法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#二分查找"><span class="nav-number">1.3.1.</span> <span class="nav-text">二分查找</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#二数之和"><span class="nav-number">1.3.2.</span> <span class="nav-text">二数之和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#反转数组"><span class="nav-number">1.3.3.</span> <span class="nav-text">反转数组</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#滑动窗口算法"><span class="nav-number">1.4.</span> <span class="nav-text">滑动窗口算法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#最小覆盖子串"><span class="nav-number">1.4.1.</span> <span class="nav-text">最小覆盖子串</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#字符串排列"><span class="nav-number">1.4.2.</span> <span class="nav-text">字符串排列</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#找所有字母异位词"><span class="nav-number">1.4.3.</span> <span class="nav-text">找所有字母异位词</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#最长无重复子串"><span class="nav-number">1.4.4.</span> <span class="nav-text">最长无重复子串</span></a></li></ol></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#twoSum问题的核心思想"><span class="nav-number">2.</span> <span class="nav-text">twoSum问题的核心思想</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#第一题"><span class="nav-number">2.1.</span> <span class="nav-text">第一题</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#第二题"><span class="nav-number">2.2.</span> <span class="nav-text">第二题</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#二分查找详解"><span class="nav-number">3.</span> <span class="nav-text">二分查找详解</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#二分搜索诗"><span class="nav-number">3.1.</span> <span class="nav-text">二分搜索诗</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#二分查找框架"><span class="nav-number">3.2.</span> <span class="nav-text">二分查找框架</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#寻找一个数：基本二分查找"><span class="nav-number">3.3.</span> <span class="nav-text">寻找一个数：基本二分查找</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#寻找左侧边界的⼆分搜索"><span class="nav-number">3.4.</span> <span class="nav-text">寻找左侧边界的⼆分搜索</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#寻找右侧边界的⼆分查找"><span class="nav-number">3.5.</span> <span class="nav-text">寻找右侧边界的⼆分查找</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#字符串乘法"><span class="nav-number">4.</span> <span class="nav-text">字符串乘法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#题目"><span class="nav-number">4.1.</span> <span class="nav-text">题目</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#思路"><span class="nav-number">4.2.</span> <span class="nav-text">思路</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#前缀和技巧"><span class="nav-number">5.</span> <span class="nav-text">前缀和技巧</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#题目："><span class="nav-number">5.1.</span> <span class="nav-text">题目：</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#解法思路："><span class="nav-number">5.2.</span> <span class="nav-text">解法思路：</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#什么是前缀和"><span class="nav-number">5.2.1.</span> <span class="nav-text">什么是前缀和</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#优化解法"><span class="nav-number">5.2.2.</span> <span class="nav-text">优化解法</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#总结"><span class="nav-number">5.3.</span> <span class="nav-text">总结</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="Li Yudong"
      src="/images/author.jpg">
  <p class="site-author-name" itemprop="name">Li Yudong</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">95</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">14</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">18</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
        <a href="https://github.com/tiarmor1" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;tiarmor1" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
      </span>
      <span class="links-of-author-item">
        <a href="mailto:1157019137@qq.com" title="E-Mail → mailto:1157019137@qq.com" rel="noopener" target="_blank"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
      </span>
  </div>
  <div class="cc-license motion-element" itemprop="license">
    <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="noopener" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a>
  </div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

        

<div class="copyright">
  
  &copy; 2020 – 
  <span itemprop="copyrightYear">2022</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Li Yudong</span>
</div>

        








      </div>
    </footer>
  </div>

  
  
  <script color='0,0,0' opacity='0.5' zIndex='-1' count='150' src="/lib1/canvas-nest/canvas-nest.min.js"></script>
  <script src="/lib1/anime.min.js"></script>
  <script src="/lib1/velocity/velocity.min.js"></script>
  <script src="/lib1/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  




  
<script src="/js/local-search.js"></script>













  

  

  
   <canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;" ></canvas> 
   <script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
   <script type="text/javascript" src="/js/fireworks.js"></script>
  
</body>
</html>

